/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年11月25日
*   描    述：
*   
================================================================*/


#include <iostream>
#include <vector>

using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if( !root )
            return 0;
        TreeNode *left = root->left;
        TreeNode *right = root->right;
        int hl = 0, hr = 0;
        while( left ){
            hl++;
            left = left->left;
        }
        while( right ){
            hr++;
            right = right->right;
        }

        if( hl == hr )
            return pow(2, hl+1) - 1;

        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};
